package graph.model;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Represents a Graph.
 * 
 * @author shankar
 * 
 */
public class Graph {
	int nVerts, nEdges;
	int v, e;

	boolean isDirected;
	boolean isWeighted;

	Vertex[] vertices;
	Edge[] edges;
	int[][] adjMatrix;

	public Graph(int nVerts, int nEdges, boolean isDirected, boolean isWeighted) {
		this.nVerts = nVerts;
		this.nEdges = nEdges;

		this.isDirected = isDirected;
		this.isWeighted = isWeighted;

		v = 0;
		e = 0;

		adjMatrix = new int[nVerts][nVerts];
		vertices = new Vertex[nVerts];
		edges = new Edge[nEdges];
	}

	public void addVertex(int key, char data) {
		vertices[v++] = new Vertex(key, data);
	}

	public void addEdge(int src, int dest) {
		addEdge(src, dest, 0);
	}

	public void addEdge(int src, int dest, int weight) {
		edges[e++] = new Edge(weight, src, dest);

		// If graph is not directed then there will be an edge from dest to src
		// as well.
		if (isDirected) {
			if (isWeighted) {
				adjMatrix[src][dest] = weight;
			} else {
				adjMatrix[src][dest] = 1;
			}
		} else {
			if (isWeighted) {
				adjMatrix[src][dest] = weight;
				adjMatrix[dest][src] = weight;
			} else {
				adjMatrix[src][dest] = 1;
				adjMatrix[dest][src] = 1;
			}

		}
	}

	public int getAdjUnVisitedVertex(int vIndex) {
		int unVisitedVertex = -1;
		for (int i = 0; i < v; i++) {
			// if there is an edge between v and i and i is not visited
			if ((adjMatrix[vIndex][i] == 1) && (vertices[i].visited == false)) {
				unVisitedVertex = i;
				break;
			}
		}
		return unVisitedVertex;
	}

	public void displayAdjacenyMatrix() {
		for (int i = 0; i < nVerts; i++) {
			for (int j = 0; j < nVerts; j++) {
				System.out.print(adjMatrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public void displayEdges() {
		for (int i = 0; i < nEdges; i++) {
			System.out.println(edges[i].src + "-->" + edges[i].dest);
		}
	}

	public void displayVertex(int v) {
		System.out.print(vertices[v].getData());
	}

	public boolean isDirected() {
		return isDirected;
	}

	public void setDirected(boolean isDirected) {
		this.isDirected = isDirected;
	}

	public Vertex[] getVertices() {
		return vertices;
	}

	public void setVertices(Vertex[] vertices) {
		this.vertices = vertices;
	}

	public Edge[] getEdges() {
		return edges;
	}

	public void setEdges(Edge[] edges) {
		this.edges = edges;
	}

	public int[][] getAdjMatrix() {
		return adjMatrix;
	}

	public void setAdjMatrix(int[][] adjMatrix) {
		this.adjMatrix = adjMatrix;
	}

	public boolean isWeighted() {
		return isWeighted;
	}

	public void setWeighted(boolean isWeighted) {
		this.isWeighted = isWeighted;
	}

	public void resetVisited() {
		for (int i = 0; i < v; i++) {
			vertices[i].setVisited(false);
		}
	}

	// --------------------Problems--------------------------------------------------------------
	public boolean isReachable(int p, int q) {
		if (p == q) {
			return true;
		}
		boolean isReachable = false;
		Stack<Integer> stack = new Stack<Integer>();
		int v = p;
		vertices[v].setVisited(true);
		stack.push(v);

		while (!stack.isEmpty()) {

			v = getAdjUnVisitedVertex(stack.peek());
			if (v == -1) {
				stack.pop();
			} else {
				if (v == q) {
					isReachable = true;
					break;
				}
				vertices[v].setVisited(true);
				stack.push(v);
			}
		}
		resetVisited();
		return isReachable;
	}

	public void printPath(int p, int q) {
		if (p == q) {
			System.out.println("Path between p and q = " + p + q);
			return;
		}

		Stack<Integer> stack = new Stack<Integer>();
		int v = p;
		vertices[v].setVisited(true);
		stack.push(v);

		while (!stack.isEmpty()) {
			v = getAdjUnVisitedVertex(stack.peek());
			if (v == -1) {
				stack.pop();
			} else {
				stack.push(v);
				vertices[v].setVisited(true);
				if (v == q) {
					break;
				}
			}
		}

		if (stack.isEmpty()) {
			System.out.println("No path");
		} else {
			for (int i = 0; i < stack.size(); i++) {
				System.out.print(vertices[stack.get(i)].getData());
			}
		}
		resetVisited();
	}
}
